package com.backpack;

public class BestTimetoBuyandSellStockIV0115_188 {
    public int maxProfit(int k, int[] prices) {

        //动态规划思路
        //dp[][] 数组含义：
        //dp[i][0]  不操作
        //dp[i][1]  下标 i 天 第一次持有股票      的最大价值
        //dp[i][2]  下标 i 天 第一次不持有股票     的最大价值
        //dp[i][3]  下标 i 天 第二次持有股票      的最大价值
        //dp[i][4]  下标 i 天 第二次不持有股票     的最大价值
        //...
        //dp[i][2k-1] 下标 i 天 第k次持有股票     的最大价值
        //dp[i][2k] 下标 i 天 第k次不持有股票     的最大价值
        //返回值 dp[prices.length - 1][2k]; 即：最后一天 第k次不持有股票（k次卖 k次出） 的最大价值
        int[][] dp = new int[prices.length][2*k+1];

        //初始化
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        dp[0][2] = 0;
//        dp[0][3] = -prices[0];
//        dp[0][4] = 0;
        for (int j = 0; j < prices.length; j++) {
            for (int i = 1; i <= 2 * k; i++) {
                if(i%2 == 1) dp[j][i] = -prices[0];
            }
        }

        //初始化 前两次持有、不持有的 最大价值
        for (int i = 1; i < prices.length; i++) {
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]); //第一次持有股票 = max( 前一天第一次持有，前一天不操作-当天股价);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i],dp[i-1][2]); //第一次不持有股票 = max(前一天持有 + i 天的股价，前一天第一次不持有）；
            if(k>1){
                dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]); //第二次持有股票 = max(前一天也持有，前一天没持有-当天股价）；
                dp[i][4] = Math.max(dp[i-1][3]+prices[i],dp[i-1][4]);   //第二次不持有股票 = max(前一天持有+当天股票，前一天第二次不持有）；
            }
        }

        if(k>1){
            for (int i = 1; i < prices.length; i++) {
                for (int j = 2; j <= k; j++) {
                    dp[i][2*j-1] = Math.max(dp[i-1][2*j-1],dp[i-1][2*(j-1)]-prices[i]); //第j次持有股票 = max( 前一天第j次持有，前一天第 j-1 次不持有-当天股价);
                    dp[i][2*j] = Math.max(dp[i-1][2*j],dp[i-1][2*j-1]+prices[i]); //第j次不持有股票 = max(前一天第j次不持有,前一天第 j 次持有 + i 天的股价）；
                }
            }
        }

        return dp[prices.length - 1][2*k];
    }
}
